package day2_linkedlist.leetcode;

import java.util.HashSet;
import java.util.Set;

public class Num142 {
    // 快慢指针法
//    public ListNode detectCycle(ListNode head) {
//        ListNode low = head,fast = head;
//        while (fast != null && fast.next != null) {
//            low = low.next;
//            fast = fast.next.next;
//            if (low == fast) {
//                ListNode third = head;
//                while (third != low) {
//                    third = third.next;
//                    low = low.next;
//                }
//                return third;
//            }
//        }
//        return null;
//    }
    // 哈希表法
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> nodeSet = new HashSet<>();
        while (head != null) {
            if (nodeSet.contains(head)) {
                return head;
            }else {
                nodeSet.add(head);
            }
            head = head.next;
        }
        return null;
    }
}
